package datastructure.tree.bst2;


/**
 * 二叉搜索树-删除节点-非递归版本
 *
 * @author 杨 强
 * @package datastructure.tree.bst2
 * @createTime 2023-03-21 21:50
 */
public class BST01Del01 {
    public static void main(String[] args) {
        /*
                        3
                       / \
                      2   4
                     /
                    1
         */
        TreeNode node1 = new TreeNode(1, "1", null, null);
        TreeNode node2 = new TreeNode(2, "2", node1, null);
        TreeNode node4 = new TreeNode(4, "4", null, null);
        TreeNode node3 = new TreeNode(3, "3", node2, node4);
        BST01Del01 bst01 = new BST01Del01(node3);

        Object delete = bst01.delete(2);
        System.out.println("应该为2,实际为:" + delete);
        // 停下来观察树
        /*
                        3
                       / \
                      1   4
         */
    }

    /**
     * 二叉搜索树的根节点
     */
    TreeNode root;

    /**
     * 构造函数-生成二叉树
     * @param root
     */
    public BST01Del01(TreeNode root) {
        this.root = root;
    }

    /**
     * 删除节点
     * @param key 删除节点的key
     * @return 删除节点的值
     */
    public Object delete(int key){
        // 找到待删除的节点
        TreeNode d = root;
        // 找到待删除节点的父节点
        TreeNode parent = null;
        while (d != null) {
            if (key < d.key) {
                parent = d;
                d = d.left;
            } else if (d.key < key) {
                parent = d;
                d = d.right;
            } else {
                break;// 找到了
            }
        }

        // 没有找到
        if (d == null){
            return null;
        }

        // 找到了, 进行删除操作
        if (d.left == null){
            // 第一种情况,左孩子为空
            shift(parent, d, d.right);
        }else if (d.right == null){
            // 第二种情况,右孩子为空
            shift(parent, d, d.left);
        }else {
            // 第四种情况,左右孩子节点都不为空
            // 1 找到被删除节点后继节点(也就是被删除节点的按照大小排序后的下一个大的节点), 这里记得看图写,不然很绕
            // 先得到删除节点的右子树的开始节点, 然后一直往左找, 就是删除节点的后继节点
            TreeNode s = d.right;
            TreeNode sParent = parent; // 后继节点的父节点
            while (s.left != null){
                sParent = s;
                s = s.left;
            }

            // 2 删除节点和后继节点不相邻,处理后继节点的子节点
            if (sParent != d) {
                // 这个时候后继节点s就是需要被删除的节点, 然后把后继节点的右孩子顶替上去
                shift(sParent, s, s.right); // 不可能有左孩子
                // 并且这个时候被删除节点的右子树应该成被删除节点的后继节点的右子树,因为最后后继节点是需要替换掉被删除节点的
                s.right = d.right;
            }

            // 3 后继取代被删除节点, 这里也是如果删除节点和后继节点相邻, 就直接后继节点替换被删除的节点就可以了.
            shift(parent, d, s);
            // 并且这个时候被删除节点的左子树应该成被删除节点的后继节点的左子树,因为最后后继节点是需要替换掉被删除节点的
            s.left = d.left;
        }
        return d.value;
    }

    /**
     * 托孤方法
     *
     * @param parent  被删除节点的父亲
     * @param deleted 被删除节点
     * @param child   被顶上去的节点
     */
    private void shift(TreeNode parent, TreeNode deleted, TreeNode child) {
        if (parent == null) {
            // 被删除节点的父节点为null,那么删除节点需要顶上去的节点之间为根节点
            root = child;
        } else if (deleted == parent.left) {
            // 被删除节点如果是自己父节点的左节点,那么被删除节点的子节点中需要顶上去的节点直接为父节点的左节点
            parent.left = child;
        } else {
            // 被删除节点如果是自己父节点的右节点,那么被删除节点的子节点中需要顶上去的节点直接为父节点的右节点
            parent.right = child;
        }
    }

}
